package com.hc.programming.math;

/**
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * 问总共有多少条不同的路径？
 * <p>
 * 示例 1：
 * <a href="./不同路径-示例1.png">示例1</a>
 * 输入：m = 3, n = 7
 * 输出：28
 * 示例 2：
 * 输入：m = 3, n = 2
 * 输出：3
 * 解释：
 * 从左上角开始，总共有 3 条路径可以到达右下角。
 * 1. 向右 -> 向下 -> 向下
 * 2. 向下 -> 向下 -> 向右
 * 3. 向下 -> 向右 -> 向下
 * 示例 3：
 * 输入：m = 7, n = 3
 * 输出：28
 * 示例 4：
 * 输入：m = 3, n = 3
 * 输出：6
 * <p>
 * 提示：
 * 1 <= m, n <= 100
 * 题目数据保证答案小于等于 2 * 10^9
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/8/31 21:47
 */
public class 不同路径 {
    public static void main(String[] args) {
        System.out.println("3,7=28--" + uniquePaths(3, 7));
        System.out.println("4,4=20--" + uniquePaths(4, 4));
        System.out.println("3,2=3--" + uniquePaths(3, 2));
        System.out.println("7,3=28--" + uniquePaths(7, 3));
        System.out.println("2,2=2--" + uniquePaths(2, 2)); // ?
        System.out.println("3,3=6--" + uniquePaths(3, 3)); // ?
        System.out.println("5,5=70--" + uniquePaths(5, 5)); // ?
        System.out.println("10,10=48620--" + uniquePaths(10, 10)); // ?
        System.out.println("13,23=548354040--" + uniquePaths(13, 23)); // ?
    }

    public static int uniquePaths(int m, int n) {
//        return 排列组合(m, n);
        return 动态规划(m, n);
    }

    /**
     * 动态规划：
     * <p>
     * dp[i][j]:走到i、j位的路径数
     * dp[i][j] = dp[i-1][j] + dp[i][j-1]
     * dp数组如何初始化: dp[1][j]、dp[i][1]全等于1
     * 遍历顺序：从前向后
     * 打印数组
     */
    private static int 动态规划(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[1][1] = 1;
        for (int i = 2; i <= m; i++) {
            dp[i][1] = 1;
        }
        for (int i = 2; i <= n; i++) {
            dp[1][i] = 1;
        }
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    public static int 排列组合(int m, int n) {
        return C(m + n - 2, m - 1);
    }

    public static int C(int m, int n) {
        long sum = 1;
        for (int i = n + 1; i <= m; i++) {
            sum *= i;
        }
        for (int i = m - n; i >= 2; i--) {
            sum /= i;
        }
        return (int) sum;
    }

}
